import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;


public class solution {

	/**
	 * Holds the list of edges in the minimum spanning tree.
	 */
	private static LinkedList<Edge> edges; 
	/**
	 * Holds the list of vertices that are known. The size of "vertices" at the end of PrimsAlgorithm() should be the same
	 * as the size of graph.vertices().  
	 */
	private static LinkedList<Vertex> knownVertices;
	
	public static void PrimsAlgorithm(SimpleGraph graph) {
		BinaryHeap heap = new BinaryHeap(); // default capacity is 10, might need to change that value
		
		Hashtable table = GraphInput.LoadSimpleGraph(graph); // table contains the vertex name (key) and the actual label of the vertex (value)
		// we need the hashtable because it contains the actual value of the the vertex
		
//		System.out.println(table); // test
//		System.out.println("Keys = " + table.keySet()); // test
//		System.out.println("Values = " + table.values()); // test
		
/*		
		Enumeration e = table.keys(); // a set of all vertices in graph
		// make appropriate modifications to the vertex
		while(e.hasMoreElements()) {
			vertexName = (String) e.nextElement();
			
//			System.out.println("Vertex " + e.nextElement()); // test
			
			// grab necessary info on vertex
			PrimVertexData data = new PrimVertexData(vertexName, (Vertex) table.get(vertexName));
//			System.out.println(data.getVertex()); // test
			// create a new vertex with a PerimVertexData object as the vertex's data
			Vertex vertex = new Vertex(data, vertexName);
			// create a node to place in the tree
			PrimHeapNode heapNode = new PrimHeapNode(vertex);
			// put the node in the binary heap
			heap.insert(heapNode);
			
//			System.out.print(heapNode.toString()); // test
		}
*/
		String vertexName; // used to capture a vertex name
		Iterator graphVert = graph.vertices();
		Vertex tempVert;
		while(graphVert.hasNext()) {
			// grab a random vertex
			tempVert = (Vertex) graphVert.next();
			vertexName = (String) tempVert.getName();
			
			// create a PrimVertexData object 
			PrimVertexData data = new PrimVertexData(vertexName, (Vertex) table.get(vertexName));
			// update the data on graph, will be used later when updating adjacent vertices
			tempVert.setData(data);
			// create a node to place in the tree
			PrimHeapNode heapNode = new PrimHeapNode(tempVert);
			// put the node in the binary heap
			heap.insert(heapNode);
		}
		// at this point, a heap has been created 
		
		heap = firstUpdateHeap(heap, graph);

		// at this point, the heap has been updated after the first arbitrary vertex has been chosen
		// all nodes in the heap that are adjacent to the first vertex have labels that point to the vertex, but are still "unknown" (known = false)
					
		// now repeat the process until this has been done (num of verteces) - 1 times
//		System.out.println("Size of heap after first update = " + heap.size()); // test			
		for (int i = 1; i < graph.numVertices() - 1; i++) {
			heap = findMinEdgeAndUpdate(heap, graph, edges);
		}
		
	}
	
	public static  BinaryHeap findMinEdgeAndUpdate(BinaryHeap heap, SimpleGraph graph, LinkedList<Edge> edges)  {
		BinaryHeap tempHeap = new BinaryHeap();
		// find the minimum edge amoung all edges that are adjacent to known vertices
		// update the heap so that there is one less node in heap and all the nodes are updated
		Iterator adjacent;
		Iterator vertIter;
		PrimHeapNode knownVert;
		Edge edge;
		
		try {
			knownVert = heap.deleteMin(); // grab the node with the smallest weight
			// if the vertex is a known vertex
			if(knownVert.isKnown()) {
				// although this may be the vertex with the smallest weight, we still have to find the correct edge that has the smallest weight
				// find all edges associated with the vertex
				adjacent = graph.incidentEdges(knownVert.vertex());
				while(adjacent.hasNext()) { // look at all edges incident to knownVert
					edge = (Edge) adjacent.next();
					Vertex v = graph.opposite(knownVert.vertex(), edge); // returns the vertex opposite of knownVert that is connected by edge e
					vertIter = knownVertices.iterator();
					while(vertIter.hasNext()) { // look at all known vertices
						if(v.getName().equals(((Vertex) vertIter.next()).getName())) { // if we found a match
							// add the edge to the list of edges in minimum spanning tree
							edges.add(edge);
						}
					}
				}
				knownVertices.add(knownVert.vertex());
			}
			else { // this should never happen
				System.err.println("ERROR!");
			}
			
			// update the heap
			
			
		} catch (EmptyHeapException e) {
			
		}
		
		return tempHeap;
	}
	
	public static BinaryHeap firstUpdateHeap(BinaryHeap heap, SimpleGraph graph) {
		BinaryHeap tempHeap = new BinaryHeap();
		Iterator adjacent; 
		PrimHeapNode knownVert; // the first vertice chosen
		
		// pick an arbitrary vertex
		try {
			knownVert = heap.deleteMin(); 
			knownVert.known(); // the vertice is now considered known
			knownVert.setWeight(0); // this is the first vertex, so the distance to itself is 0
			
			// add the first vertex to the list of known vertices
			knownVertices.add(knownVert.vertex());
			
//			System.out.println("First vertice chosen is " + knownVert.toString()); // test
//			System.out.println("Size of heap before first update = " + heap.size()); // test
			
			// look for the adjacent vertices in the heap
			while(!heap.isEmpty()) { // for every node in the heap
//				System.out.println("Heap is not empty"); // test
				PrimHeapNode tempNode = heap.deleteMin(); // grab a node
//				System.out.println("Node to find adjacent vertices with = " + tempNode.getName()); // test
				// update all vertices adjacent to knownVert
				adjacent = graph.incidentEdges(knownVert.vertex()); // used to find all incident edges
//				System.out.println("Does this node have adjacencies? " + adjacent.hasNext());
				while(adjacent.hasNext()) {
					// find the vertex connected to the known vertex with the given edge
					Edge e = (Edge) adjacent.next();
//					System.out.println("test"); // test
					Vertex v = graph.opposite(knownVert.vertex(), e); // returns a vertex
					// get name of the vertex
					String adjName = (String) v.getName();
					// if we find a vertex adjacent to knownVert
					if(adjName.equals(tempNode.vertex().getName())) {
						System.out.println("Adjacent to " + knownVert.vertex().getName() + " = " + tempNode.vertex().getName()); // test
						// update the weight in tempNode
						tempNode.setWeight((Double) e.getData());
						tempNode.setLabel(knownVert.getName());
						tempNode.known(); // the node is considerered known
						break;
					}
				}
				tempHeap.insert(tempNode);
			}
			// all the nodes in heap are gone! But all the nodes in tempHeap are an updated version of heap.

//			System.out.println("test"); // test
			
//			System.out.println("Size of heap after first update = " + tempHeap.size()); // test
			
		} catch (EmptyHeapException e1) {
		}
		return tempHeap;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		/*
		 * Create a class called PrimVertexData that will be used for the "data" field for Vertex class.  
		 * 
		 * Create a class called PrimHeapNode that will be used for BinaryHeap. The BinaryHeap object will be an array of PrimHeapNode objects. 
		 * How will a PrimHeapNode 
		 * 
		 * Each vertex should have two labels, 1) nearest tree vertex and 2) length (the weight) of the corresponding edge.  You might need boolean "known" and a reference to the node in the heap. 
		 * 
		 *  Vertices not adjacent to any of the tree vertices can be given the infinite label and null label for name of the nearest tree vertex
		 */
		SimpleGraph graph = new SimpleGraph();
		
		PrimsAlgorithm(graph);
		
	}

}
